package mess;

import java.util.*;

public class LeeCode_40 {
    public static void main(String[] args) {
        int[] nums = new int[]{10,1,2,7,6,1,5};
        int[] nums2 = new int[]{1,1,1,1,1};
//        System.out.println(combinationSum2(nums, 8));
        System.out.println(combinationSum2(nums2, 1));
    }

    private static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        System.out.println(Arrays.toString(candidates));
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrick(result, candidates, list, target, 0, 0);
        return result;
    }
    private static void backTrick(List<List<Integer>> result, int[] candidates, List<Integer> list, int target, int index, int sum){
        if (sum == target){
            result.add(new ArrayList<>(list));
            return;
        }
        int len = candidates.length;
        for (int i = index; i < len && sum + candidates[i] <= target; i++) {
            if (i > index && candidates[i] == candidates[i - 1])
                continue;
            list.add(candidates[i]);
            sum += candidates[i];
            backTrick(result, candidates, list, target, i + 1, sum);
            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
    }
}
